package org.apache.lucene.search;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.io.IOException;
import java.util.List;

import org.apache.lucene.index.IndexReader;
import org.apache.lucene.search.BooleanClause.Occur;

/* Description from Doug Cutting (excerpted from
 * LUCENE-1483):
 *
 * BooleanScorer uses an array to score windows of
 * 2K docs. So it scores docs 0-2K first, then docs 2K-4K,
 * etc. For each window it iterates through all query terms
 * and accumulates a score in table[doc%2K]. It also stores
 * in the table a bitmask representing which terms
 * contributed to the score. Non-zero scores are chained in
 * a linked list. At the end of scoring each window it then
 * iterates through the linked list and, if the bitmask
 * matches the boolean constraints, collects a hit. For
 * boolean queries with lots of frequent terms this can be
 * much faster, since it does not need to update a priority
 * queue for each posting, instead performing constant-time
 * operations per posting. The only downside is that it
 * results in hits being delivered out-of-order within the
 * window, which means it cannot be nested within other
 * scorers. But it works well as a top-level scorer.
 *
 * The new BooleanScorer2 implementation instead works by
 * merging priority queues of postings, albeit with some
 * clever tricks. For example, a pure conjunction (all terms
 * required) does not require a priority queue. Instead it
 * sorts the posting streams at the start, then repeatedly
 * skips the first to to the last. If the first ever equals
 * the last, then there's a hit. When some terms are
 * required and some terms are optional, the conjunction can
 * be evaluated first, then the optional terms can all skip
 * to the match and be added to the score. Thus the
 * conjunction can reduce the number of priority queue
 * updates for the optional terms. */

final class BooleanScorer extends Scorer {

    private static final class BooleanScorerCollector extends Collector {
        private BucketTable bucketTable;
        private int mask;
        private Scorer scorer;

        public BooleanScorerCollector(int mask, BucketTable bucketTable) {
            this.mask = mask;
            this.bucketTable = bucketTable;
        }

        @Override
        public void collect(final int doc) throws IOException {
            final BucketTable table = bucketTable;
            final int i = doc & BucketTable.MASK;
            final Bucket bucket = table.buckets[i];

            if (bucket.doc != doc) { // invalid bucket
                bucket.doc = doc; // set doc
                bucket.score = scorer.score(); // initialize score
                bucket.bits = mask; // initialize mask
                bucket.coord = 1; // initialize coord

                bucket.next = table.first; // push onto valid list
                table.first = bucket;
            } else { // valid bucket
                bucket.score += scorer.score(); // increment score
                bucket.bits |= mask; // add bits in mask
                bucket.coord++; // increment coord
            }
        }

        @Override
        public void setNextReader(IndexReader reader, int docBase) {
            // not needed by this implementation
        }

        @Override
        public void setScorer(Scorer scorer) throws IOException {
            this.scorer = scorer;
        }

        @Override
        public boolean acceptsDocsOutOfOrder() {
            return true;
        }

    }

    // An internal class which is used in score(Collector, int) for setting the
    // current score. This is required since Collector exposes a setScorer method
    // and implementations that need the score will call scorer.score().
    // Therefore the only methods that are implemented are score() and doc().
    private static final class BucketScorer extends Scorer {

        float score;
        int doc = NO_MORE_DOCS;
        int freq;

        public BucketScorer(Weight weight) {
            super(weight);
        }

        @Override
        public int advance(int target) throws IOException {
            return NO_MORE_DOCS;
        }

        @Override
        public int docID() {
            return doc;
        }

        @Override
        public float freq() {
            return freq;
        }

        @Override
        public int nextDoc() throws IOException {
            return NO_MORE_DOCS;
        }

        @Override
        public float score() throws IOException {
            return score;
        }

    }

    static final class Bucket {
        int doc = -1; // tells if bucket is valid
        float score; // incremental score
        // TODO: break out bool anyProhibited, int
        // numRequiredMatched; then we can remove 32 limit on
        // required clauses
        int bits; // used for bool constraints
        int coord; // count of terms in score
        Bucket next; // next valid bucket
    }

    /** A simple hash table of document scores within a range. */
    static final class BucketTable {
        public static final int SIZE = 1 << 11;
        public static final int MASK = SIZE - 1;

        final Bucket[] buckets = new Bucket[SIZE];
        Bucket first = null; // head of valid list

        public BucketTable() {
            // Pre-fill to save the lazy init when collecting
            // each sub:
            for (int idx = 0; idx < SIZE; idx++) {
                buckets[idx] = new Bucket();
            }
        }

        public Collector newCollector(int mask) {
            return new BooleanScorerCollector(mask, this);
        }

        public int size() {
            return SIZE;
        }
    }

    static final class SubScorer {
        public Scorer scorer;
        // TODO: re-enable this if BQ ever sends us required clauses
        //public boolean required = false;
        public boolean prohibited;
        public Collector collector;
        public SubScorer next;

        public SubScorer(Scorer scorer, boolean required, boolean prohibited, Collector collector, SubScorer next) throws IOException {
            if (required) {
                throw new IllegalArgumentException("this scorer cannot handle required=true");
            }
            this.scorer = scorer;
            // TODO: re-enable this if BQ ever sends us required clauses
            //this.required = required;
            this.prohibited = prohibited;
            this.collector = collector;
            this.next = next;
        }
    }

    private SubScorer scorers = null;
    private BucketTable bucketTable = new BucketTable();
    private final float[] coordFactors;
    // TODO: re-enable this if BQ ever sends us required clauses
    //private int requiredMask = 0;
    private final int minNrShouldMatch;
    private int end;
    private Bucket current;
    private int doc = -1;

    // Any time a prohibited clause matches we set bit 0:
    private static final int PROHIBITED_MASK = 1;

    BooleanScorer(Weight weight, boolean disableCoord, Similarity similarity, int minNrShouldMatch, List<Scorer> optionalScorers, List<Scorer> prohibitedScorers, int maxCoord) throws IOException {
        super(weight);
        this.minNrShouldMatch = minNrShouldMatch;

        if (optionalScorers != null && optionalScorers.size() > 0) {
            for (Scorer scorer : optionalScorers) {
                if (scorer.nextDoc() != NO_MORE_DOCS) {
                    scorers = new SubScorer(scorer, false, false, bucketTable.newCollector(0), scorers);
                }
            }
        }

        if (prohibitedScorers != null && prohibitedScorers.size() > 0) {
            for (Scorer scorer : prohibitedScorers) {
                if (scorer.nextDoc() != NO_MORE_DOCS) {
                    scorers = new SubScorer(scorer, false, true, bucketTable.newCollector(PROHIBITED_MASK), scorers);
                }
            }
        }

        coordFactors = new float[optionalScorers.size() + 1];
        for (int i = 0; i < coordFactors.length; i++) {
            coordFactors[i] = disableCoord ? 1.0f : similarity.coord(i, maxCoord);
        }
    }

    // firstDocID is ignored since nextDoc() initializes 'current'
    @Override
    protected boolean score(Collector collector, int max, int firstDocID) throws IOException {
        // Make sure it's only BooleanScorer that calls us:
        assert firstDocID == -1;
        boolean more;
        Bucket tmp;
        BucketScorer bs = new BucketScorer(weight);

        // The internal loop will set the score and doc before calling collect.
        collector.setScorer(bs);
        do {
            bucketTable.first = null;

            while (current != null) { // more queued 

                // check prohibited & required
                if ((current.bits & PROHIBITED_MASK) == 0) {

                    // TODO: re-enable this if BQ ever sends us required
                    // clauses
                    //&& (current.bits & requiredMask) == requiredMask) {

                    // TODO: can we remove this?  
                    if (current.doc >= max) {
                        tmp = current;
                        current = current.next;
                        tmp.next = bucketTable.first;
                        bucketTable.first = tmp;
                        continue;
                    }

                    if (current.coord >= minNrShouldMatch) {
                        bs.score = current.score * coordFactors[current.coord];
                        bs.doc = current.doc;
                        bs.freq = current.coord;
                        collector.collect(current.doc);
                    }
                }

                current = current.next; // pop the queue
            }

            if (bucketTable.first != null) {
                current = bucketTable.first;
                bucketTable.first = current.next;
                return true;
            }

            // refill the queue
            more = false;
            end += BucketTable.SIZE;
            for (SubScorer sub = scorers; sub != null; sub = sub.next) {
                int subScorerDocID = sub.scorer.docID();
                if (subScorerDocID != NO_MORE_DOCS) {
                    more |= sub.scorer.score(sub.collector, end, subScorerDocID);
                }
            }
            current = bucketTable.first;

        } while (current != null || more);

        return false;
    }

    @Override
    public int advance(int target) throws IOException {
        throw new UnsupportedOperationException();
    }

    @Override
    public int docID() {
        throw new UnsupportedOperationException();
    }

    @Override
    public int nextDoc() throws IOException {
        throw new UnsupportedOperationException();
    }

    @Override
    public float score() {
        throw new UnsupportedOperationException();
    }

    @Override
    public void score(Collector collector) throws IOException {
        score(collector, Integer.MAX_VALUE, -1);
    }

    @Override
    public String toString() {
        StringBuilder buffer = new StringBuilder();
        buffer.append("boolean(");
        for (SubScorer sub = scorers; sub != null; sub = sub.next) {
            buffer.append(sub.scorer.toString());
            buffer.append(" ");
        }
        buffer.append(")");
        return buffer.toString();
    }

    @Override
    protected void visitSubScorers(Query parent, Occur relationship, ScorerVisitor<Query, Query, Scorer> visitor) {
        super.visitSubScorers(parent, relationship, visitor);
        final Query q = weight.getQuery();
        SubScorer sub = scorers;
        while (sub != null) {
            // TODO: re-enable this if BQ ever sends us required
            //clauses
            //if (sub.required) {
            //relationship = Occur.MUST;
            if (!sub.prohibited) {
                relationship = Occur.SHOULD;
            } else {
                // TODO: maybe it's pointless to do this, but, it is
                // possible the doc may still be collected, eg foo
                // OR (bar -fee)
                relationship = Occur.MUST_NOT;
            }
            sub.scorer.visitSubScorers(q, relationship, visitor);
            sub = sub.next;
        }
    }

}
